1. Technical Field
This invention relates to a system and method for computing the probability of false alarms when using histogram matching to find objects in images.
2. Background Art
Using histograms for finding objects in images is attractive because histograms are relatively insensitive to an object""s pose and scale, background clutter, and partial occlusion. However, this insensitivity is also prone to produce false matches with regions of the background that happen to match the object""s histogram well enough, resulting in an algorithm that xe2x80x9cfindsxe2x80x9d an object in an image even when it is not really there. These false alarms can be caused by using too few histogram bins, a subimage for matching so that is too large, or a matching threshold that is too low. Therefore, it is important to be able to quantify the false alarm probability for histogram matching so that intelligent tradeoffs can be made between the aforementioned parameters and the false alarm rate. To date prior histogram matching systems have not had this capability.
It is noted that in the remainder of the specification, the description refers to various individual publications identified by a numeric designator contained within a pair of brackets. For example, such a reference may be identified by reciting, xe2x80x9creference [1]xe2x80x9d or simply xe2x80x9c[1]xe2x80x9d. A listing of the publications corresponding to each designator can be found at the end of the Detailed Description section.
The present invention overcomes the aforementioned limitations in prior histogram matching systems by a system and method that computes the probability of histogram matching false alarms for different settings of a histogram matching algorithm""s parameters. This allows the algorithm""s designer to clearly see the tradeoffs and adjust the parameters to produce the optimum capability with the lowest possible false alarm rate. In one embodiment of the present invention, the false alarm rate of histogram matching is exactly computed by listing all the histograms possible as a function of the number of bins and counts, determining those that could cause a false alarm, and summing their probabilities. This exact method is particularly useful because it applies to any method used for comparing histograms. In another embodiment of the system and method according to the present invention, the summed multinomial distribution is approximated by a multivariate normal distribution that is numerically integrated to provide an efficient approximation of the false alarm probability.
The fundamental component of computing a false alarm probability for histogram matching is computing the probability that clutter in a background image will produce a histogram that matches sufficiently well with a model histogram. As will be discussed below, this can be done if an assumption is made about the probability distribution of pixels (or, more generally features) in the background. In particular, it is assumed that the background pixels are independent and identically distributed (iid). Given this assumption, the probability of occurrence of any histogram is given by a multinomial distribution. The system and method according to the present invention provides an exact calculation of false alarm probability for images that are iid, and provides an approximate calculation for image features that are approximately iid.
A histogram may be represented as a vector H=(h1, h2, . . . , hm). This histogram has m different bins, with hi being a non-negative integer telling how many counts are in bin i. The bins of the histogram usually represent a set of ranges of pixel values of gray level or color, but they could also be other quantized features. The procedure for computing a histogram is to first quantize the original image into m different values and then histogram this quantized image.
The process of recognizing an object with a histogram starts with a model of the object. A prototype histogram Hp=(hp,1,hp,2, . . . , hm) is computed from the model image of the object. A test histogram Ht=(ht,1, ht,2, . . . , ht,m) is computed from an image or subimage that may or may not contain the object. This test histogram may come from a region of the image that is larger, smaller, or the same size as the image used to compute the model histogram. These two histograms are tested for similarity in some way, and if they are similar enough, then the object is declared found in the test image. It is possible to use test images that are the same size as the model images, and therefore only one comparison per image is needed. Or it is possible to scan through the image, extracting several subimages and comparing each of the subimages"" histograms to the model histogram. The system and method according to the present invention seeks to compute the probability for matching one of these subimages when that subimage does not represent the object being sought.
There have been several histogram similarity measures proposed. A simple one is the histogram intersection. The intersection tells how many counts in the model histogram the test histogram accounts for. If the intersection exceeds a certain threshold then the histograms are considered similar enough to declare the object found in the image. A convenient threshold is that the test histogram should account for some large fraction of the counts in the model histogram. If the test histogram does account for a large fraction of the counts in the model histogram then the object will be declared found. A false alarm occurs when the intersection equals or exceeds the match threshold when the object does not really exist in the image or portion of the image under consideration. This image or subimage is referred to a background image because it does not contain the object of interest.
The procedure for approximating the false alarm probability is to list the histograms of those background images that cause a false alarm and sum their probabilities of occurrence In order to accomplish this task, it is possible to think of the set of all possible histograms that an image of a given size could produce. Some of these histograms can cause a false alarm. If the total number of possible histograms is small enough, they can all be listed in order to find which ones will cause a false alarm. The probabilities of occurrence of the histograms in this subset can be summed to yield the false alarm probability. For example, every possible histogram computed from an image with n pixels will have n total counts spread among m bins. Each bin will have a nonnegative number of the counts. Thus, for the simple case of a histogram with m=2, the number of possible histograms would be n+1. For example, if the number of pixels n=5, then the six possible histograms are (0,5), (1,4), (2,3), (4,1) and (5,0). For m=3 bins, there are                     ∑        n                              h          1                =        0              ⁢                            ∑                      n            -                          h              1                                                            h            2                    =          0                    ⁢      1        =            1      2        ⁢          (              n        +        1            )        ⁢          (              n        +        2            )      
possible histograms. Note that the index variables are the histogram counts. For n=5, the 21 possible histograms are
In general, the number of distinct possible histograms with m bins and n counts, may be expressed by the equation:       N    ⁡          (              m        ,        n            )        =            1                        (                      m            -            1                    )                ⁢        l              ⁢                            ∏                      m            -            1                                    i          =          1                    ⁢              (                  n          +          i                )            
and the histograms themselves can be generated from all the index values (h1, h2, . . . , hm) taken on by running through the following nested sums:                     ∑        n                              h          1                =        0              ⁢                            ∑                      n            -                          h              1                                                            h            2                    =          0                    ⁢                                    ∑                          n              -                              h                1                            -                              h                2                                                                        h              3                        =            0                          ⁢                  …          ⁢                                                    ∑                                  n                  -                                      h                    1                                    -                                      h                    2                                    -                  …                  -                                      h                                          m                      -                      2                                                                                                                    h                                      m                    -                    1                                                  =                0                                      ⁢                          
                        ⁢                          with              ⁢                              xe2x80x83                            ⁢                              h                m                                                          =      n    -          h      1        -          h      2        -    …    -                  h                  m          -          1                    .      
The paragraphs above gave a technique for listing all possible histograms with m bins and n counts. Next the probability of occurrence of a background histogram (h1, h2, . . . , hm) is computed. The pixels in the quantized image can take on values of {1, 2 . . . , m}, and we say the probability of a single pixel taking on value i is pi. The probability of a given pixel occurring when the probability is summed over all pixels must equal 1; therefore,                     ∑        m                    i        =        1              ⁢          p      i        =  1.
It is assumed that the pixels in a background image are independent and identically distributed. The probability of a given histogram occurring can be shown to be given by the multinomial distribution:   "AutoLeftMatch"                                          p            ⁡                          (              H              )                                =                    ⁢                      p            ⁡                          (                                                h                  1                                ,                                  h                  2                                ,                …                ⁢                                  xe2x80x83                                ,                                                      h                    m                                    ;                                      p                    1                                                  ,                                  p                  2                                ,                …                ⁢                                  xe2x80x83                                ,                                  p                  m                                ,                n                            )                                                                    =                    ⁢                                    (                                                                    n                                                                                                                                                                                            h                            1                                                                                                                                h                            2                                                                                                    …                                                                                                      h                            m                                                                                                                                                          )                        ⁢                          p              1                              h                1                                      ⁢                          p              2                              h                2                                      ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          p              m                              h                m                                                        
Based on the matching criterion employed, some subset {Hfalse alarm} of all possible background histograms will exceed the matching threshold and produce a false alarm. The probability of a false alarm when matching a model histogram to the histogram of a single test image or subimage is then       ∑                  i        ·                  H          1                    ∈              (                  H                      false            ⁢                          xe2x80x83                        ⁢            alarm                          )              ⁢            p      ⁡              (                  H          i                )              .  
The number of possible histograms grows quickly with the size of the image and the number of quantization levels. The large number of histograms means it is usually impractical to list them all and sum their probabilities as discussed above. Hence, the system and method according to the present invention seeks to approximate the probability in these cases. This is done by integrating a multivariate normal, instead of summing multinomial probabilities, where the mean and covariance of the multivariate normal are the same as the mean and covariance of the multinomial. The probabilities given by the multinomial distribution can be approximated by a multivariate normal with the same mean and covariance as the multinomial. That is,   "AutoLeftMatch"                                          p            ⁡                          (              H              )                                =                    ⁢                                    (                                                                    n                                                                                                                                                                                            h                            1                                                                                                                                h                            2                                                                                                    …                                                                                                      h                            m                                                                                                                                                          )                        ⁢                          p              1                              h                1                                      ⁢                          p              2                              h                2                                      ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢                          p              m                              h                m                                                                                  ≈                    ⁢                                    1                                                                    (                                          2                      ⁢                      π                                        )                                                                              (                                              m                        -                        1                                            )                                        /                    2                                                  ⁢                                                      "LeftBracketingBar"                    Σ                    "RightBracketingBar"                                                        1                    /                    2                                                                        ⁢                          exp              ⁡                              [                                                      -                                          xe2x80x83                                        ⁢                                          1                      2                                                        ⁢                                                            (                                                                        H                          xe2x80x2                                                -                        μ                                            )                                        T                                    ⁢                                                            Σ                                              -                        1                                                              ⁡                                          (                                                                        H                          xe2x80x2                                                -                        μ                                            )                                                                      ]                                                                                  =                    ⁢                      g            ⁡                          (              H              )                                          
where Hxe2x80x2 is a vector of all but the last bin of the histogram H:             H      xe2x80x2        =                  (                              h            1                    ,                      h            2                    ,          …          ⁢                      xe2x80x83                    ,                      h                          m              -              1                                      )            T            μ    =                  n        ⁡                  (                                    p              1                        ,                          p              2                        ,            …            ⁢                          xe2x80x83                        ,                          p                              m                -                1                                              )                    T            Σ    =                            [                      Σ            ij                    ]                                      (                          m              -              1                        )                    xc3x97                      (                          m              -              1                        )                              =              {                                                                                                                        np                      i                                        ⁡                                          (                                              1                        -                                                  p                          i                                                                    )                                                                                                                                  if                      ⁢                                              xe2x80x83                                            ⁢                      i                                        =                    j                                                                                                                                          -                                              np                        i                                                              ⁢                                          p                      j                                                                                                                                  if                      ⁢                                              xe2x80x83                                            ⁢                      i                                        ≠                    j                                                                        ⁢                          
                        ⁢                          Σ                              -                1                                              =                                                    [                                                      Σ                    ⋓                                    ij                                ]                                                              (                                      m                    -                    1                                    )                                xc3x97                                  (                                      m                    -                    1                                    )                                                      =                          {                                                                                                                                                                                                      1                              n                                                        ⁢                                                          (                                                                                                1                                                                      p                                    i                                                                                                  +                                                                  1                                                                      p                                    m                                                                                                                              )                                                                                                                                                                                          if                              ⁢                                                              xe2x80x83                                                            ⁢                              i                                                        =                            j                                                                                                                                                                            1                                                          np                              m                                                                                                                                                                                          if                              ⁢                                                              xe2x80x83                                                            ⁢                              i                                                        ≠                            j                                                                                                                ⁢                                          
                                        ⁢                                          "LeftBracketingBar"                      Σ                      "RightBracketingBar"                                                        =                                                            n                                              m                        -                        1                                                              ⁢                                                                                            ∏                          m                                                                          i                          =                          1                                                                    ⁢                                                                        p                          i                                                ⁢                                                  
                                                ⁢                        For                        ⁢                                                  xe2x80x83                                                ⁢                        all                        ⁢                                                  xe2x80x83                                                ⁢                        of                        ⁢                                                  xe2x80x83                                                ⁢                        the                        ⁢                                                  xe2x80x83                                                ⁢                        above                                                                                            ,                i                ,                                  j                  ∈                                                            {                                              1                        ,                        2                        ,                        …                        ⁢                                                  xe2x80x83                                                ,                                                  m                          -                          1                                                                    }                                        .                                                                                          
This approximation assumes that the number of counts in each bin is large. Using this approximation, the system and method according to the present invention computes the false alarm probability by integrating a multivariate normal rather than summing multinomial probabilities.       ∫          H      ∈              {                  H                      false            ⁢                          xe2x80x83                        ⁢            alarm                          }              ⁢            g      ⁡              (        H        )              ⁢          ⅆ      H      
This can be easier than summing by using efficient numerical approximation techniques for computing the integral. Both Monte Carlo integration and Mathematica""s standard numerical integration function have been used in tested embodiments. The integration limits cover those histograms that would cause a false alarm, which is a function of the method used for comparing histograms. One method that gives simple integration limits is the following. For the model or prototype histogram Hp=(hp,1, hp,2, . . . , hp,m) and test histogram Ht=(ht,1, ht,2, . . . , ht,m), it might be said that all the entries in the test histogram have to equal or exceed some large fraction xcex1:0 less than xcex1xe2x89xa61 of the corresponding entries in the prototype histogram. The set of histograms producing a false alarm is then       {          H              false        ⁢                  xe2x80x83                ⁢        alarm              }    =      {                  H        t            ⁢              :            ⁢                        (                                    h                              t                ,                1                                      ≥                          α              ⁢                              xe2x80x83                            ⁢                              h                                  p                  ,                  1                                                              )                ⋀                  (                                    h                              t                ,                2                                      ≥                          α              ⁢                              xe2x80x83                            ⁢                              h                                  p                  ,                  2                                                              )                ⋀        …        ⋀                  (                                    h                              t                ,                m                                      ≥                          α              ⁢                              xe2x80x83                            ⁢                              h                                  p                  ,                  m                                                              )                      }  
The false alarm probability can then be approximated by       ∫                  α        ⁢                  xe2x80x83                ⁢                  h                      p            ,            1                              -      0.5        ∝    ⁢            ∫                        α          ⁢                      xe2x80x83                    ⁢                      h                          p              ,              2                                      -        0.5            ∝        ⁢          xe2x80x83        ⁢          …      ⁢              xe2x80x83            ⁢                        ∫                                    α              ⁢                              xe2x80x83                            ⁢                              h                                  p                  ,                                      m                    -                    1                                                                        -            0.5                    ∝                ⁢                              g            ⁡                          (              H              )                                ⁢                      ⅆ                          h              1                                ⁢                      ⅆ                          h              2                                ⁢                      xe2x80x83                    ⁢          …          ⁢                      xe2x80x83                    ⁢                      ⅆ                          h                              m                -                1                                                        
The foregoing analysis can be used to adjust the parameters of an object recognition algorithm that uses histogram matching, or any other application that uses histogram matching. The false alarm rate is ultimately a function of the algorithm""s parameters (e.g. window size, number of bins). The system and method according to the present invention can be used to compute the false alarm rate for any setting of parameters. The parameters are then adjusted to bring the false alarm rate down to an acceptable level.
As discussed above, the above exact multinomial and approximation methods of determining false alarm probabilities work well when the probability distribution of pixels (or, more generally features) in the background of the image are independent and identically distributed (iid). However, it is also possible for the system and method according to the present invention to accurately predict histogram matching false alarm probabilities for non-iid images. This may be done by distorting the image to make it more iid-like and then using the system and method according to the present invention to determine the optimum parameters to be used in the histogram matching for the iid converted image.